package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//回溯法
//N皇后难点：全局状态变量的判断，需要判断每行、每列、每条左对角线、每条右对角线，特别是2条左右对角线
//左对角线："\"，2n-1条，可以用r-i表示（一条斜线上的点r-i都相等）
//右对角线："/"，2n-1条，可以用r+i表示（一条斜线上的点r+i都相等）
public class LC51NQueens {
    public List<List<String>> solveNQueens(int n) {
        //base case
        if (n<=0) {
            return new ArrayList<>();
        }
        //棋盘
        List<String> board = new ArrayList<>(n);
        //初始化棋盘，一开始全是空位
        for (int i = 0; i < n; i++) {
            StringBuilder sb=new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append("."); //.表示空位
            }
            board.add(sb.toString());
        }
        //全局状态变量，用 Set 比 boolean数组 灵活通用，不需要找出对角线和行列的精确关系
        Set<Integer> row = new HashSet<>(n); //行
        Set<Integer> column = new HashSet<>(n); //列
        Set<Integer> leftCross = new HashSet<>(2*n-1); //左对角线
        Set<Integer> rightCross = new HashSet<>(2*n-1); //右对角线
        //回溯，决策树——先行后列
        List<List<String>> res = new ArrayList<>();
        backtrack(n, board, row, column, leftCross, rightCross, 0, res);

        return res;
    }

    public void backtrack(int n, List<String> board, Set<Integer> row, Set<Integer> column, Set<Integer> leftCross, Set<Integer> rightCross,
                          int r, List<List<String>> res) {
        //找到答案
        if (r>=n) {
            res.add(new ArrayList<>(board));
            return;
        }
        //未找到答案，继续下一行，尝试每个列
        if (row.contains(r)) {
            return;
        }
        for (int c = 0; c < n; c++) {
            if (column.contains(c) || leftCross.contains(r-c) || rightCross.contains(r+c)) {
                continue;
            }
            StringBuilder sb = new StringBuilder(board.get(r)); //string是不可变类型，使用string builder进行修改
            sb.setCharAt(c, 'Q');  //Q表示皇后
            board.set(r, sb.toString());
            row.add(r);
            column.add(c);
            leftCross.add(r-c);
            rightCross.add(r+c);
            backtrack(n, board, row, column, leftCross, rightCross, r+1, res);
            //恢复修改
            sb = new StringBuilder(board.get(r));
            sb.setCharAt(c, '.');
            board.set(r, sb.toString());
            row.remove(r);
            column.remove(c);
            leftCross.remove(r-c);
            rightCross.remove(r+c);
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC51NQueens().solveNQueens(4));
    }
}
